Exercise: Scapegoat Trees - Data Structures with Generic Types in Python

Task#

Modify the add(x) method of the ScapegoatTree so that it does not waste any time recomputing the sizes of subtrees that have already been computed. This is possible because, by the time the method wants to compute size(w), it has already computed one of size(w.left) or size(w.right).

Sample input

The sample input will be as follows:

Expected output

The expected output will be as follows:

Tree contents:
1 3 4 5 7 8 9 
Tree after removing 4:
1 3 5 7 8 9

main.py

arrayqueue.py

binarytree.py

binarysearchtree.py

utils.py

base.py

import math
from utils import new_array
from binarysearchtree import BinarySearchTree
# log function
def log32(q):
    return int(math.log(q, 1.5))
# Main class
class ScapegoatTree(BinarySearchTree):
    def __init__(self):
        super(ScapegoatTree, self).__init__()
        self._initialize()
    # Initialize function
    def _initialize(self):
        self.n = 0
        self.q = 0
    # Function to remove values
    def remove(self, x):
        if super(ScapegoatTree, self).remove(x):
            if 2*self.n < self.q:
                self.rebuild(self.r)
                self.q = self.n
            return True
        return False
    # Function to add values in depth        
    def add_with_depth(self, x):
        u = self._new_node(x)
        w = self.r
        if w == self.nil:
            self.r = u
            self.n += 1
            self.q += 1

Enter to Rename, Shift+Enter to Preview

Task to implement the add() method for ScapegoatTrees